package algo.A03_递归和算法复杂度;

import util.ArrayUtil;

import java.util.Arrays;

/**
 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
 *
 * 输入一个从小到大排序的数组的一个旋转，输出旋转数组的最小元素。
 *
 * 例如数组[3,4,5,1,2]为[1,2,3,4,5]的一个旋转，该数组的最小值为1。
 */
public class T11_旋转数组的最小数字_二分法 {
    public static void main(String[] args) {
        //生成随机不重复数组
        int[] arr = ArrayUtil.getRandomArrWithoutRepetition(10, 1, 20);
        //升序排序
        Arrays.sort(arr);
        //输出原始数组
        ArrayUtil.print(arr);
        //移动前n个元素到后面
        arr = move(arr, 9);
        //输出移动后的数组
        ArrayUtil.print(arr);
        //开始解题
        int result = solution(arr);
        System.out.println("result = " + result);
    }

    private static int solution(int[] arr){
        int begin = 0;
        int end = arr.length - 1;
        //如果压根没有旋转，直接返回第一个元素
        if (arr[begin] < arr[end]){
            return arr[begin];
        }
        //当begin和end相邻时，退出循环
        while (begin + 1 < end){
            int mid = begin + (end - begin) / 2;
            //要么左侧有序，要么右侧有序
            if (arr[mid] >= arr[begin]){//中间值大于第一个数时，左侧有序，最小值在右侧
                begin = mid;
            }else {//中间值小于第一个数时，右侧有序，最小值在左侧
                end = mid;
            }
        }
        return arr[end];
    }

    /**
     * 将数组前n个元素移动到数组末尾
     */
    private static int[] move(int[] arr,int n){
        for (int i = 0; i < n; i++) {
            int moveNumber = arr[0];
            for (int j = 0; j < arr.length - 1; j++) {
                arr[j] = arr[j + 1];
            }
            arr[arr.length - 1] = moveNumber;
        }
        return arr;
    }
}
